#include <vector>
#include <iostream>
using namespace std;
bool compare(vector<int> v1, vector<int> v2)
{
    return sqrt(v1[0] * v1[0] + v1[1] * v1[1]) < sqrt(v2[0] * v2[0] + v2[1] * v2[1]);
}
class Solution
{
public:
    int maxEnvelopes(vector<vector<int> > &envelopes)
    {
        int len = envelopes.size();
        if (len < 1)
            return len;
        // 由于现在是二维的，可以利用对角线性质，降维，退化成
        // 一维的最长上升子序列
        sort(envelopes.begin(), envelopes.end(), compare);
        vector<int> diagonal(len);
        for (int i = 0; i < len; i++)
        {
            diagonal[i] = sqrt(envelopes[i][0] * envelopes[i][0] + envelopes[i][1] * envelopes[i][1]);
            cout << diagonal[i] << endl;
        }
        vector<int> d(len + 1, 0);
        int ret = 1;
        d[ret] = diagonal[0];
        for (int i = 0; i < len; i++)
        {
            if (diagonal[i] > d[ret])
                d[++ret] = diagonal[i];
            else
            {
                int l = 1, r = ret, pos = 0;
                while (l <= r)
                {
                    int mid = (l + r) >> 1;
                    if (d[mid] < diagonal[i])
                    {
                        pos = mid;
                        l = mid + 1;
                    }
                    else
                    {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = diagonal[i];
            }
        }
        return ret;
    }
};

bool compare(vector<int> v1, vector<int> v2)
{
    return sqrt(v1[0] * v1[0] + v1[1] * v1[1]) < sqrt(v2[0] * v2[0] + v2[1] * v2[1]);
}
class Solution
{
public:
    int maxEnvelopes(vector<vector<int> > &envelopes)
    {
        int len = envelopes.size();
        if (len < 1)
            return len;
        // 由于现在是二维的，可以利用对角线性质，降维，退化成
        // 一维的最长上升子序列
        sort(envelopes.begin(), envelopes.end(), compare);

        vector<int> dp(len);
        dp[0] = 1;
        int maxnum = dp[0];
        for (int i = 1; i < len; i++)
        {
            dp[i] = 1;
            for (int j = 0; j < i; j++)
            {
                if (envelopes[j][0] >= envelopes[i][0] || envelopes[j][1] >= envelopes[i][1])
                    continue;
                dp[i] = max(dp[i], dp[j] + 1);
            }
            maxnum = max(dp[i], maxnum);
        }
        return maxnum;
    }
};

class Solution
{
public:
    int get_ans(int nums[], int n)
    {
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;
        int dp[n];
        dp[0] = nums[0];
        int left = 0, right = 0;
        for (int i = 1; i < n; i++)
        {
            int l = left, r = right;
            while (l <= r)
            {
                int mid = (l + r) / 2;
                if (dp[mid] < nums[i])
                    l = mid + 1;
                else
                    r = mid - 1;
            }
            if (l < n)
            {
                dp[l] = nums[i];
                right = max(right, l);
            }
        }
        return right - left + 1;
    }
    int maxEnvelopes(vector<vector<int> > &envelopes)
    {
        sort(envelopes.begin(), envelopes.end(), [](vector<int> &a, vector<int> &b) {
            if (a[0] == b[0])
                return a[1] > b[1];
            else
                return a[0] < b[0];
        });
        int n = envelopes.size();
        int nums[n + 1];
        for (int i = 0; i < n; i++)
        {
            nums[i] = envelopes[i][1];
        }
        return get_ans(nums, n);
    }
};